package code1.dp;

import java.util.Arrays;

/**
 * 原题链接：https://leetcode.cn/problems/last-stone-weight-ii/
 */
public class P1049 {

    //尽可能的把石头分成重量相等的两堆,两堆石头的重量差即为最终剩下的重量
    //转化为0-1背包问题，即用容量为总重量一半的背包最多能装多重的石头
    //物品的重量与价值均为stones[i]
    //dp[j]表示容量为j能装的最大质量
    public int lastStoneWeightII(int[] stones) {
        int[] dp=new int[15001];
        int sum = Arrays.stream(stones).sum();
        int target=sum/2;
        for(int i=0;i<stones.length;i++){
            for(int j=target;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[target]-dp[target];
    }
}
